package alg20250227;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Text2 {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> hash1 = new HashMap<>();
        Map<String, Integer> hash2 = new HashMap<>();
        int m = words[0].length();
        int n = s.length();
        List<Integer> ret = new ArrayList<>();
        for(String word : words){
            hash1.put(word, hash1.getOrDefault(word, 0) + 1);
        }
        for (int left = 0, right = 0, count = 0; right < n; right += m) {
            //进窗口
            String inWord = s.substring(right, right + m);
            hash2.put(inWord, hash2.getOrDefault(inWord, 0) + 1);
            //维护count
            if(hash2.get(inWord) <= hash1.get(inWord)) count++;

            //判断
            if(right - left + 1 > words.length * m){
                //出窗口
                String outWord = s.substring(left, left + m);
                if(hash2.get(outWord) <= hash1.get(outWord)) count--;
                hash2.put(outWord, hash2.get(outWord) - 1);
                if(hash2.get(outWord) == 0) hash2.remove(outWord);
            }
            //更新结果
            if(count == words.length){
                ret.add(left);
            }
        }
        return ret;
    }
}
